<HTML>
<!--
  -- Copyright (c) 1996-1999
  -- Silicon Graphics Computer Systems, Inc.
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Silicon Graphics makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -- Copyright (c) 1994
  -- Hewlett-Packard Company
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Hewlett-Packard Company makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -->
<Head>
<Title>Random Number Generator</Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
	ALINK="#ff0000"> 
<IMG SRC="CorpID.gif" 
     ALT="SGI" HEIGHT="43" WIDTH="151"> 
<!--end header-->
<BR Clear>
<H1>Random Number Generator</H1>

<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "functors.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
<TD Align=right><Img src = "concept.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: functors</TD>
<TD Align=right VAlign=top><b>Component type</b>: concept</TD>
</TR>
</Table>

<h3>Description</h3>
A Random Number Generator is a <A href="functors.html">function object</A> that can be used to 
generate a random sequence of integers.  That is: if <tt>f</tt> is a Random
Number Generator and <tt>N</tt> is a positive integer, then <tt>f(N)</tt> will return
an integer less than <tt>N</tt> and greater than or equal to <tt>0</tt>.  If <tt>f</tt> is 
called many times with the same value of <tt>N</tt>, it will yield a sequence
of numbers that is uniformly distributed <A href="#1">[1]</A> in the range <tt>[0, N)</tt>. <A href="#2">[2]</A>
<h3>Refinement of</h3>
<A href="UnaryFunction.html">Unary Function</A>
<h3>Associated types</h3>
<Table border>
<TR>
<TD VAlign=top>
Argument type
</TD>
<TD VAlign=top>
The type of the Random Number Generator's argument.  This must
   be an integral type.
</TD>
</TR>
<TR>
<TD VAlign=top>
Result type
</TD>
<TD VAlign=top>
The type returned when the Random Number Generator is called.  It must
   be the same as the argument type.
</TD>
</tr>
</table>
<h3>Notation</h3>
<Table>
<TR>
<TD VAlign=top>
<tt>F</tt>
</TD>
<TD VAlign=top>
A type that is a model of Random Number Generator.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>Integer</tt>
</TD>
<TD VAlign=top>
The argument type of <tt>F</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>f</tt>
</TD>
<TD VAlign=top>
Object of type <tt>F</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>N</tt>
</TD>
<TD VAlign=top>
Object of type <tt>Integer</tt>
</TD>
</tr>
</table>
<h3>Definitions</h3>
The <i>domain</i> of a Random Number Generator (<i>i.e.</i> the set
of permissible values for its argument) is the set of numbers that are
greater than zero and less than some maximum value.
<P>
The <i>range</i> of a Random Number Generator is the set of nonnegative
integers that are less than the Random Number Generator's argument.
<h3>Valid expressions</h3>
None, except for those defined by <A href="UnaryFunction.html">Unary Function</A>.
<h3>Expression semantics</h3>
<Table border>
<TR>
<TH>
Name
</TH>
<TH>
Expression
</TH>
<TH>
Precondition
</TH>
<TH>
Semantics
</TH>
<TH>
Postcondition
</TH>
</TR>
<TR>
<TD VAlign=top>
Function call
</TD>
<TD VAlign=top>
<tt>f(N)</tt>
</TD>
<TD VAlign=top>
<tt>N</tt> is positive.
</TD>
<TD VAlign=top>
Returns a pseudo-random number of type <tt>Integer</tt>. <A href="#2">[2]</A>
</TD>
<TD VAlign=top>
The return value is less than <tt>N</tt>, and greater than or equal to 0.
</TD>
</tr>
</table>
<h3>Complexity guarantees</h3>
<h3>Invariants</h3>
<Table border>
<TR>
<TD VAlign=top>
Uniformity
</TD>
<TD VAlign=top>
In the limit as <tt>f</tt> is called many times with the same argument
<tt>N</tt>, every integer in the range <tt>[0, N)</tt> will appear an equal number
of times.
</TD>
</tr>
</table>
<h3>Models</h3>
<h3>Notes</h3>
<P><A name="1">[1]</A>
Uniform distribution means that all of the numbers in the range
<tt>[0, N)</tt> appear with equal frequency.  Or, to put it differently,
the probability for obtaining any particular value is <tt>1/N</tt>.
<P><A name="2">[2]</A>
Random number generators are a very subtle subject: a good random
number generator must satisfy many statistical properties beyond
uniform distribution.  See section 3.4 of Knuth for a discussion of
what it means for a sequence to be random, and section 3.2 for several
algorithms that may be used to write random number generators.
(D. E. Knuth, <i>The Art of Computer
Programming.  Volume 2: Seminumerical Algorithms</i>, third edition.  
Addison-Wesley, 1998.)
<h3>See also</h3>

<!--start footer--> 
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54" 
        ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif" 
        HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright &copy; 
1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML> 
